在一開始學習golang的時候，會注意到一個跟其他語言不太一樣的資料結構 slice

在A Tour of Go裡面介紹提到

An array has a fixed size. A slice, on the other hand, is a dynamically-sized, flexible view into the elements of an array. In practice, slices are much more common than arrays.

這個資料形態是一個動態的array，可以隨意的添加或是刪除陣列的長度
但既然他是陣列，表示他在宣告的時候是先跟系統取得了一個固定的空間來儲存固定長度的連續資料
那為什麼會有介紹文章說在slice中添加一個資料的時間複雜度是O(1)

在一般的程式中，如果宣告了一個陣列，當把資料放到陣列中
Before [null,null,null,null,null]
After ["aa",null,null,null,null]

這樣的時間複雜度就是1

但如果狀況是
Before ["aa","bb","cc","dd","ee"]
After ["aa","bb","cc","dd","ee","ff"]

這個在程式中要做的是
開一個新的長度為6的陣列
[null,null,null,null,null,null]
接著把["aa","bb","cc","dd","ee"]放到陣列裡面
變成
["aa","bb","cc","dd","ee",null]
最後再把"ff"放到陣列中
["aa","bb","cc","dd","ee","ff"]

這個操作本身就是O(n)

那為什麼會說golang的append資料到slice裡面的時間複雜度是O(1)呢

在golang裡面，他基本上也是走上面的流程，長度不夠會開一個新的空間來搬移
但他不是每次都剛好開一格，而是每次都多開一倍的空間

舉例
(1) [null]
(1) ["aa"]
(2) ["aa",null] ["aa","bb"]
(3) ["aa","bb",null,null] ["aa","bb","cc",null]
(1) ["aa","bb","cc","dd"]
(5) ["aa","bb","cc","dd",null,null,null,null] ["aa","bb","cc","dd","ee",null,null,null]
(1) ["aa","bb","cc","dd","ee","ff",null,null]
(1) ["aa","bb","cc","dd","ee","ff","gg",null]
(1) ["aa","bb","cc","dd","ee","ff","gg","hh"]

可以觀察到，當空間足夠的時候，所進行的操作的成本是1，只有需要增加空間的時候，成本才會變成n

假設與定義
1. 初始容量：假設初始容量為 1。
2. 擴容策略：每當容量不足時，容量翻倍。
3. 總操作次數：假設有 n 次 append 操作。

每次擴容的成本分析
每次擴容時，需要將現有的 k 個元素複製到新的陣列中，花費 O(k) 的時間。
我們需要計算在 n 次 append 操作中，總的複製成本。
總複製成本計算

1. 擴容次數：從容量 1 開始，每次翻倍，直到容量達到或超過 n。擴容次數約為 log₂ n。
2. 每次擴容的複製成本：
   • 第 1 次擴容：複製 1 個元素。
   • 第 2 次擴容：複製 2 個元素。
   • 第 3 次擴容：複製 4 個元素。
   • …
   • 第 k 次擴容：複製 2^(k-1) 個元素。
3. 總複製成本：
   這是一個公比為 2 的等比數列，其和可以表示為：

總複製的成本是n-1

每次 append 操作的固定成本為 O(1)。
總的固定成本為 O(n)

所以總成本就是
O(n)+O(n)

而添加的元素是n個
(O(n)+O(n))/n = O(1)

所以這個時間複雜度是平均出來的結果